package demo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

public class Solution2 {
    public int minTime(int n, int[][] edges) {
        // 构建邻接表
        Map<Integer, List<Edge>> graph = new HashMap<>();
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], start = edge[2], end = edge[3];
            graph.putIfAbsent(u, new ArrayList<>());
            graph.get(u).add(new Edge(v, start, end));
        }
        
        // 优先队列，按照到达时间排序
        PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.time - b.time);
        pq.offer(new Node(0, 0));
        
        // 记录到达每个节点的最小时间
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[0] = 0;
        // 如果队列不为空
        while (!pq.isEmpty()) {
            Node curr = pq.poll();
            int u = curr.id, time = curr.time;
            
            // 如果已经找到更优解，跳过
            if (time > dist[u]) continue;
            
            // 到达目标节点
            if (u == n - 1) return time;
            
            // 可以选择等待1个单位时间
            if (time + 1 < dist[u]) {
                dist[u] = time + 1;
                pq.offer(new Node(u, time + 1));
            }
            
            // 遍历所有出边
            if (graph.containsKey(u)) {
                for (Edge edge : graph.get(u)) {
                    int v = edge.to;
                    int start = edge.start;
                    int end = edge.end;
                    
                    // 如果当前时间在边的时间窗口内
                    if (time >= start && time <= end) {
                        int arrivalTime = time + 1;
                        if (arrivalTime < dist[v]) {
                            dist[v] = arrivalTime;
                            pq.offer(new Node(v, arrivalTime));
                        }
                    }
                    // 如果当前时间小于开始时间，可以等待到开始时间
                    else if (time < start) {
                        int arrivalTime = start + 1;
                        if (arrivalTime < dist[v]) {
                            dist[v] = arrivalTime;
                            pq.offer(new Node(v, arrivalTime));
                        }
                    }
                }
            }
        }

        printArray(dist);
        return dist[n - 1] == Integer.MAX_VALUE ? -1 : dist[n - 1];
    }
    
    class Edge {
        int to, start, end;
        Edge(int to, int start, int end) {
            this.to = to;
            this.start = start;
            this.end = end;
        }
    }

    private void printArray(int[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }
    
    class Node {
        int id, time;
        Node(int id, int time) {
            this.id = id;
            this.time = time;
        }
    }

    public static void main(String[] args) {
        int n = 4;
        int[][] edges = {{0, 1, 0,3}, {1,3,7,8}, {0,2,1,5}, {2,3,4,7}};
        Solution2 solution2 = new Solution2();
        int result = solution2.minTime(n, edges);
        System.out.println(result);
    }
}